import java.util.HashMap;
import java.util.Map;

public class PathSum {
    // leetcode 路径总和III
    // https://leetcode.cn/problems/path-sum-iii/description/?envType=study-plan-v2&envId=top-100-liked
    public int pathSum(TreeNode root, int targetSum) {
        // 前缀和
        Map<Long, Integer> prefix = new HashMap<>();
        prefix.put(0L,1);
        return dfs(root, prefix, 0, targetSum);
    }

    private int dfs(TreeNode root, Map<Long, Integer> prefix, long curr, int targetSum) {
        if (root == null) return 0;

        curr += root.val;
        int ret = prefix.getOrDefault(curr - targetSum, 0);
        prefix.put(curr, prefix.getOrDefault(curr,0) + 1);
        ret += dfs(root.left, prefix, curr, targetSum);
        ret += dfs(root.right, prefix, curr, targetSum);
        prefix.put(curr, prefix.getOrDefault(curr, 0) - 1);
        return ret;
    }
}
